package br.ufmg.vod.test;


import java.io.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Arrays;
import java.util.Collection;
import java.util.Map;
import java.util.Properties;
import java.util.Set;

import javolution.util.FastList;
import javolution.util.FastSet;
import br.ufmg.vod.collections.IntArrayWrapper;
import br.ufmg.vod.collections.XRangeCollection;
import br.ufmg.vod.wbr.EdgeUtil;
import br.ufmg.vod.wbr.IOUtil;
import edu.uci.ics.jung.algorithms.cluster.WeakComponentClusterer;
import edu.uci.ics.jung.algorithms.metrics.Metrics;
import edu.uci.ics.jung.algorithms.shortestpath.DijkstraDistance;
import edu.uci.ics.jung.graph.DirectedGraph;
import edu.uci.ics.jung.graph.util.EdgeType;
import edu.uci.ics.jung.graph.util.Pair;

public class FastJungDirectedGraph implements DirectedGraph<Integer, Long>{
	
	private static final int INT_SIZE = 4;
	private static final int IDX_REGISTER_SIZE = 2*INT_SIZE;
	
	private static final int WBR_NUM_DOCS = 5939061;
//	private static final int SAMPLE_SIZE = 1024*1024 +1; //1/5 da colecao
//	private static final boolean SAMPLE = true;
	
	private int[][] inEdges;
	private int[][] outEdges;

	private long maxInDegree;
	private long maxOutDegree;
	private int edgeCount;
	private int numVertex;
	private int[][] neighbours;
	private final boolean sample;
	private final int sampleSize;
	
	

	public FastJungDirectedGraph(String inLinkIdxFilename, String inLinkDataFilename
			, String outLinkIdxFilename, String outLinkDataFilename, boolean sample, int sampleSize ) throws IOException{
	
		this.sample = sample;
		this.sampleSize = sampleSize;
		//Open data holders
		File inLinkIdxFile = new File(inLinkIdxFilename);
		File outLinkIdxFile = new File(outLinkIdxFilename);
		BufferedInputStream inLinkIdx = new BufferedInputStream(new FileInputStream(inLinkIdxFile));
		BufferedInputStream inLinkData = new BufferedInputStream(new FileInputStream(inLinkDataFilename));
		BufferedInputStream outLinkIdx = new BufferedInputStream(new FileInputStream(outLinkIdxFile));
		BufferedInputStream outLinkData = new BufferedInputStream(new FileInputStream(outLinkDataFilename));
		
		//assert everything is as expected
		assert inLinkIdxFile.length() == outLinkIdxFile.length();
		assert inLinkIdxFile.length() > 0;
		assert inLinkIdxFile.length()/IDX_REGISTER_SIZE < Integer.MAX_VALUE;
		assert inLinkIdxFile.length()/IDX_REGISTER_SIZE == WBR_NUM_DOCS;

		//do the hard part
		this.loadData(inLinkIdxFile, inLinkData, inLinkIdx, outLinkIdxFile, outLinkData, outLinkIdx);
		this.compact();
		this.initializeNeighours();
		
		//clean yourself up!
		inLinkIdx.close();
		inLinkData.close();
		outLinkIdx.close();
		outLinkData.close();
	}


	private void loadData(File inLinkIdxFile, BufferedInputStream inLinkData, BufferedInputStream inLinkIdx, File outLinkIdxFile, BufferedInputStream outLinkData, BufferedInputStream outLinkIdx) throws IOException,
			FileNotFoundException {
		
		this.numVertex = (int) (sample ? sampleSize : inLinkIdxFile.length()/(IDX_REGISTER_SIZE));
		int bufferSize = (int) (sample ? (numVertex+1)*IDX_REGISTER_SIZE : inLinkIdxFile.length());
		
		this.inEdges = new int[numVertex][];
		this.outEdges = new int[numVertex][];
		
		
		byte[] inLinkIdxbuffer = new byte[bufferSize];
		byte[] outLinkIdxbuffer = new byte[bufferSize];
		IOUtil.fillBuffer(inLinkIdx, inLinkIdxbuffer);
		IOUtil.fillBuffer(outLinkIdx, outLinkIdxbuffer);
		
		System.out.println(inLinkIdxFile.length()+" "+inLinkIdxbuffer.length);
		this.maxInDegree = 0l;
		this.maxOutDegree= 0l;
		this.edgeCount = 0;

		

		System.out.println("Will read "+ numVertex +" lists...");		
		for (int i = 0; i < numVertex; i++) {
			
			if( i%(1024*1024) == 0)	System.out.println(i/(1024*1024)+" giga lists...");

			//inEdges
			int startOffset = IOUtil.readSignedInt(inLinkIdxbuffer, i*IDX_REGISTER_SIZE);
			int endOffset = IOUtil.readSignedInt(inLinkIdxbuffer, (i+1)*IDX_REGISTER_SIZE);
			assert startOffset <= endOffset;
			byte[] buffer = new byte[(int) (endOffset-startOffset)];
			IOUtil.fillBuffer(inLinkData, buffer);
			this.inEdges[i] = IOUtil.toSignedInts(buffer);
			Arrays.sort(this.inEdges[i]);
			maxInDegree = this.inEdges[i].length > maxInDegree ? this.inEdges[i].length : maxInDegree;
			
	
			//outEdges
			startOffset = IOUtil.readSignedInt(outLinkIdxbuffer, i*IDX_REGISTER_SIZE);
			endOffset = IOUtil.readSignedInt(outLinkIdxbuffer, (i+1)*IDX_REGISTER_SIZE);
			buffer = new byte[(int) (endOffset-startOffset)];
			IOUtil.fillBuffer(outLinkData, buffer);
			this.outEdges[i]=IOUtil.toSignedInts(buffer);
			Arrays.sort(this.outEdges[i]);
			maxOutDegree = this.outEdges[i].length > maxOutDegree ? this.outEdges[i].length : maxOutDegree;
			
			this.edgeCount+=this.outEdges[i].length;
		}
		
		System.out.println("maxInDegree="+maxInDegree);
		System.out.println("maxOutDegree="+maxOutDegree);
	}

	@Override
	public boolean addEdge(Long e, Integer v1, Integer v2) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean addEdge(Long e, Integer v1, Integer v2, EdgeType edgeType) {
		throw new UnsupportedOperationException();
	}

	@Override
	public Integer getDest(Long directed_edge) {
		return EdgeUtil.getDest(directed_edge);
	}

	@Override
	public Pair<Integer> getEndpoints(Long edge) {
		return new Pair<Integer>(EdgeUtil.getSource(edge), EdgeUtil.getDest(edge));
	}

	@Override
	public Collection<Long> getInEdges(Integer vertex) {
		FastList<Long> inEdges = new FastList<Long>();
		int u = vertex;
		for (int i = 0; i < this.inEdges[vertex].length; i++) {
			inEdges.add(EdgeUtil.generateEdgeId(u, this.inEdges[vertex][i]));
		}
		return inEdges;
	}

	@Override
	public Integer getOpposite(Integer vertex, Long edge) {
		return EdgeUtil.isSource(vertex, edge) ? EdgeUtil.getSource(edge) : EdgeUtil.getDest(edge);
	}

	@Override
	public Collection<Long> getOutEdges(Integer vertex) {
		FastList<Long> outEdges = new FastList<Long>();
		int u = vertex;
		for (int i = 0; i < this.outEdges[vertex].length; i++) {
			outEdges.add(EdgeUtil.generateEdgeId(u, this.outEdges[vertex][i]));
		}
		return outEdges;
	}

	@Override
	public int getPredecessorCount(Integer vertex) {
		return this.inDegree(vertex);
	}

	@Override
	public Collection<Integer> getPredecessors(Integer vertex) {
		return new IntArrayWrapper(this.inEdges[vertex]);
	}

	@Override
	public Integer getSource(Long directed_edge) {
		return EdgeUtil.getSource(directed_edge);
	}

	@Override
	public int getSuccessorCount(Integer vertex) {
		return this.outDegree(vertex);
	}

	@Override
	public Collection<Integer> getSuccessors(Integer vertex) {
		return new IntArrayWrapper(this.outEdges[vertex]);
	}

	@Override
	public int inDegree(Integer vertex) {
		return this.inEdges[vertex].length;
	}

	@Override
	public boolean isDest(Integer vertex, Long edge) {
		return EdgeUtil.isSource(vertex, edge);
	}

	@Override
	public boolean isPredecessor(Integer v1, Integer v2) {
		if( this.inEdges[v2].length < this.outEdges[v1].length ){
			return Arrays.binarySearch(this.inEdges[v2], v1) != -1;
		}else{
			return Arrays.binarySearch(this.outEdges[v1], v2) != -1;
		}
	}

	@Override
	public boolean isSource(Integer vertex, Long edge) {
		return EdgeUtil.isSource(vertex, edge);
	}

	@Override
	public boolean isSuccessor(Integer v1, Integer v2) {
		if( this.inEdges[v1].length < this.outEdges[v2].length ){
			return Arrays.binarySearch(this.inEdges[v1], v2) != -1;
		}else{
			return Arrays.binarySearch(this.outEdges[v2], v1) != -1;
		}
	}

	@Override
	public int outDegree(Integer vertex) {
		return this.outEdges[vertex].length;
	}

	@Override
	public boolean addEdge(Long edge, Collection<? extends Integer> vertices) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean addEdge(Long edge, Collection<? extends Integer> vertices,
			EdgeType edge_type) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean addVertex(Integer vertex) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean containsEdge(Long edge) {
		int u = EdgeUtil.getSource(edge);
		int v = EdgeUtil.getDest(edge);
		return isPredecessor(u, v);
	}

	@Override
	public boolean containsVertex(Integer vertex) {
		return vertex >= 0 && vertex < this.outEdges.length;
	}

	@Override
	public int degree(Integer vertex) {
		return this.inDegree(vertex)+this.outDegree(vertex);
	}

	@Override
	public Long findEdge(Integer v1, Integer v2) {
		return EdgeUtil.generateEdgeId(v1, v2);
	}

	@Override
	public Collection<Long> findEdgeSet(Integer v1, Integer v2) {
		throw new UnsupportedOperationException();
	}

	@Override
	public int getEdgeCount() {
		return this.edgeCount;
	}

	@Override
	public int getEdgeCount(EdgeType edge_type) {
		return  edge_type == EdgeType.DIRECTED ? this.edgeCount : 0;
	}

	@Override
	public EdgeType getEdgeType(Long edge) {
		return EdgeType.DIRECTED;
	}

	@Override
	public Collection<Long> getEdges() {
		throw new UnsupportedOperationException();
	}

	@Override
	public Collection<Long> getEdges(EdgeType edge_type) {
		throw new UnsupportedOperationException();
	}

	@Override
	public int getIncidentCount(Long edge) {
		return EdgeUtil.getSource(edge) == EdgeUtil.getDest(edge) ? 1 : 2;
	}

	@Override
	public Collection<Long> getIncidentEdges(Integer vertex) {
		FastSet<Long> edges = new FastSet<Long>();
		edges.addAll(this.getInEdges(vertex));
		edges.addAll(this.getOutEdges(vertex));
		return edges;
	}

	@Override
	public Collection<Integer> getIncidentVertices(Long edge) {
		int[] v = {EdgeUtil.getSource(edge), EdgeUtil.getDest(edge)};
		return new IntArrayWrapper(v);
	}

	@Override
	public int getNeighborCount(Integer vertex) {
		return getNeighbors(vertex).size();
	}

	@Override
	public Collection<Integer> getNeighbors(Integer vertex) {
		
		if( this.neighbours == null ){
		
			FastSet<Integer> neighbours = new FastSet<Integer>();
			int u = vertex;
			for (int i = 0; i < this.inEdges[u].length; i++) {
				neighbours.add(this.inEdges[u][i]);
			}
			for (int i = 0; i < this.outEdges[u].length; i++) {
				neighbours.add(this.outEdges[u][i]);
			}
			return neighbours;
		}else{
			return new IntArrayWrapper(this.neighbours[vertex]);
		}
	}

	@Override
	public int getVertexCount() {
		return this.numVertex;
	}

	@Override
	public Collection<Integer> getVertices() {
		return new XRangeCollection(0, this.numVertex);
	}

	@Override
	public boolean isIncident(Integer vertex, Long edge) {
		return EdgeUtil.getDest(edge) == vertex ||EdgeUtil.getSource(edge) == vertex;
	}

	@Override
	public boolean isNeighbor(Integer v1, Integer v2) {
		if( this.neighbours == null )
			return this.isPredecessor(v1, v2) || this.isPredecessor(v2, v1);
		else
			return Arrays.binarySearch(this.neighbours[v1], v2) != -1;
	}

	@Override
	public boolean removeEdge(Long edge) {
		throw new UnsupportedOperationException();
	}

	@Override
	public boolean removeVertex(Integer vertex) {
		throw new UnsupportedOperationException();
	}
	
	public void compact(){
		for (int u = 0; u < this.numVertex; u++) {
			
			//inEdges
			int[] oldArray = this.inEdges[u];
			for (int i = 0; i < oldArray.length; i++) {
				if( oldArray[i] >= this.numVertex ){
					int[] newArray = new int[i];
					System.arraycopy(oldArray, 0, newArray, 0, i);
					this.inEdges[u] = newArray;
					break;
				}
			}
			
			//outEdges
			oldArray = this.outEdges[u];
			for (int i = 0; i < oldArray.length; i++) {
				if( oldArray[i] >= this.numVertex ){
					int[] newArray = new int[i];
					System.arraycopy(oldArray, 0, newArray, 0, i);
					this.outEdges[u] = newArray;
					this.edgeCount-= (oldArray.length-i);
					break;
				}
			}
		}
	}
	
	public void initializeNeighours(){
		this.neighbours = new int[this.numVertex][];
		for (int i = 0; i < numVertex; i++) {
			FastSet<Integer> set = new FastSet<Integer>();
			for (int j = 0; j < this.inEdges[i].length; j++) {
				set.add(this.inEdges[i][j]);
			}
			for (int j = 0; j < this.outEdges[i].length; j++) {
				set.add(this.outEdges[i][j]);
			}
			this.neighbours[i] = new int[set.size()];
			int j = 0;
			for (int v : set) {
				this.neighbours[i][j++] = v;
			}
			Arrays.sort(this.neighbours[i]);
		}
	}
	
	
	public static void main(String[] args) throws IOException {
		
		Properties props = new Properties(); 
		props.load(ClassLoader.getSystemResourceAsStream("collection.properties"));
		String inLinkIdx = props.getProperty("collection.path")+props.getProperty("inlinks.idx");
		String inLink = props.getProperty("collection.path")+props.getProperty("inlinks");
		String outLinkIdx = props.getProperty("collection.path")+props.getProperty("outlinks.idx");
		String outLink = props.getProperty("collection.path")+props.getProperty("outlinks");
		System.out.println(props);
		
		long start = System.currentTimeMillis();
		FastJungDirectedGraph graph = new FastJungDirectedGraph(inLinkIdx, inLink, outLinkIdx, outLink, true, 2*1024*1024);
		System.out.printf("graphContructor: %.3f seconds.\n",(System.currentTimeMillis()-start)/1000f);
		System.out.printf("VertexCount=%d EdgeCount=%d\n", graph.numVertex, graph.edgeCount);
		graph.compact();
		System.out.printf("graphCompact: %.3f seconds.\n",(System.currentTimeMillis()-start)/1000f);
		System.out.printf("VertexCount=%d EdgeCount=%d\n", graph.numVertex, graph.edgeCount);
		
		graph.initializeNeighours();
		System.out.printf("initializeNeighours: %.3f seconds.\n",(System.currentTimeMillis()-start)/1000f);
		System.out.printf("VertexCount=%d EdgeCount=%d\n", graph.numVertex, graph.edgeCount);
//		
//		BFSDistanceLabeler<Integer, Long> bfsLabeler = new BFSDistanceLabeler<Integer, Long>();
//		bfsLabeler.labelDistances(graph, 0);
//		System.out.printf("bfs: %.3f seconds.\n",(System.currentTimeMillis()-start)/1000f);
//		System.out.printf("VertexVisited=%d\n", bfsLabeler.getVerticesInOrderVisited().size());
		
//		System.out.printf("start Metrics.clusteringCoefficients: %.3f seconds.\n",(System.currentTimeMillis()-start)/1000f);
//		Map<Integer, Double> clusteringCoefficients = Metrics.clusteringCoefficients(graph);
//		System.out.printf("Metrics.clusteringCoefficients: %.3f seconds.\n",(System.currentTimeMillis()-start)/1000f);
//		
//		System.out.printf("start wwc.transform: %.3f seconds.\n",(System.currentTimeMillis()-start)/1000f);
//		WeakComponentClusterer<Integer, Long> wwc = new WeakComponentClusterer<Integer, Long>();
//		Set<Set<Integer>> clustered = wwc.transform(graph);
//		System.out.printf("wwc.transform: %.3f seconds.\n",(System.currentTimeMillis()-start)/1000f);
//		System.out.println("NumClusters="+clustered.size());
//		int maxCluster = 0;
//		for (Set<Integer> set : clustered) {
//			maxCluster = Math.max(maxCluster, set.size());
//		}
//		System.out.println(maxCluster);
//		for (int i = 0; i < graph.numVertex; i++) {
//			DijkstraDistance<Integer, Long> dijkstra = new DijkstraDistance<Integer, Long>(graph);
//			Map<Integer, Number> distanceMap = dijkstra.getDistanceMap(0);
//			System.out.printf("dijkstra.getDistanceMap: %.3f seconds.\n",(System.currentTimeMillis()-start)/1000f);			
//		}
		
//		DijkstraDistance<Integer, Long> dijkstra = new DijkstraDistance<Integer, Long>(graph);
//		Map<Integer, Number> distanceMap = dijkstra.getDistanceMap(0);

	}

}
